package _18_剑指OfferII;

import java.util.HashMap;
import java.util.Map;

public class _066_剑指OfferII单词之和 {
    
    Map<String, Integer> containers;
    
    Node first;

    /** Initialize your data structure here. */
    public _066_剑指OfferII单词之和() {
        containers = new HashMap<>();
        first = new Node();
    }

    public void insert(String key, int val) {
        if (containers.put(key, val) == null) {
            insert(key);
        }
    }

    public int sum(String prefix) {
        return findWordsTotal(prefix);
    }

    public void insert(String word) {
        Node node = first;
        // 逆序存储
        int len = word.length();
        for (int i = 0; i < len; ++i) {
            char cur = word.charAt(i);
            Node[] children = node.children;
            if (children == null) children = node.children = new Node[26];
            Node child = children[cur - 'a'];
            if (child != null) {
                node = child;
                continue;
            }
            Node newNode = new Node();
            // 新建
            children[cur - 'a'] = newNode;
            node = newNode;
        }
        node.word = true;
        node.str = word;
    }

    public int findWordsTotal(String prefix) {
        Node node = first;
        // 逆序存储
        int len = prefix.length();
        for (int i = 0; i < len; ++i) {
            char cur = prefix.charAt(i);
            Node[] children = node.children;
            if (children == null) return 0;
            Node child = children[cur - 'a'];
            if (child != null) {
                node = child;
                continue;
            }
            return 0;
        }
        // 接下来深度寻找单词
        return dfs(node);
    }

    private int dfs(Node node) {
        int total = 0;
        if (node.word) {
            total += containers.get(node.str);
        }
        Node[] nodes = node.children;
        if (nodes == null) return total;
        for (Node value : nodes) {
            if (value != null) {
                total += dfs(value);
            }
        }
        return total;
    }

    static class Node {

        Node[] children;

        boolean word;

        String str;

    }
    
}
